package sort;

public class AshSortPlus {
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();

		int[] estimateArray = new int[(list.length<<1) + list.length];
		for(int i=0; i<estimateArray.length; i++) estimateArray[i] = -1;
		
		for(int i=0; i<list.length; i++){
			int start = list[i]<<1;

			do {
				start++;
			} while(list[i] >= estimateArray[start] && estimateArray[start] != -1);
				
			if(estimateArray[start] == -1) estimateArray[start] = list[i];
			else insertNum(list[i], start, estimateArray);
		}

	    for(int i=0, j=0; i < list.length; i++, j++){
	    	while(estimateArray[j] == -1) j++;
		    list[i] = estimateArray[j];
	    }
	    
		return (System.currentTimeMillis()-startTime);
	}
	
	public static void insertNum(int num, int pos, int[] list){
		int start = pos+1;
		while(list[start] != -1) start++;
		
		while(start != pos) list[start] = list[--start];
		list[pos] = num;
	}
}